package com.leetcode;

import ds.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No106
 * @description 106. 从中序与后序遍历序列构造二叉树
 * @date 2021/3/9 下午7:54
 */
public class No106 {

    public static void main(String[] args) {

    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0){
            return null;
        }
        // 存放中序遍历的对应位置
        Map<Integer,Integer> index = new HashMap<>();
        for(int i = 0;i < inorder.length;i++){
            index.put(inorder[i],i);
        }
        TreeNode res = buildTree(0,inorder.length - 1,0,postorder.length - 1,inorder,postorder,index);
        return res;

    }

    private static TreeNode  buildTree(int inS,int inE,int postS,int postEnd,int[] inorder,int[] postorder,Map<Integer,Integer> index){
        if(inE < inS || postEnd < postS){
            return null;
        }
        int val = postorder[postEnd];
        // 分界点
        int rootVal = index.get(val);
        TreeNode root = new TreeNode(val);
        root.left = buildTree(inS,rootVal - 1,postS,postS + rootVal - inS - 1,inorder,postorder,index);
        root.right = buildTree(rootVal + 1,inE,postS + rootVal - inS,postEnd - 1,inorder,postorder,index);
        return root;

    }



}
